package com.heima.leetcode.datastructure.linkedlist;

import static com.heima.leetcode.datastructure.linkedlist.MergeTwoList.*;

/**
 * <h2>合并多个有序链表</h2>
 */
public class MergeLists {

    /**
     * 对外界提供的合并数组方法
     * @param lists 要合并的链表头节点构成的数组
     * @return 合并后的链表的头节点
     */
    public static ListNode mergeLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        return mergeLists(lists, 0, lists.length - 1);
    }

    /**
     * <h3>方法一，递归</h3>
     * 递的时候将lists拆分split，终止条件是不能再拆分，归的时候两两合并
     * @param lists 存放链表头的数组
     * @param i 数组左边界
     * @param j 数组右边界
     * @return 合并后的数组
     * <br>
     * <br>
     * <h3>Divide and Conquer 分而治之（多路递归，分成多个子问题进行求解）</h3>
     * <h3>Decrease and Conquer 减而治之（数据规模变小，比如二分查找）</h3>
     */
    private static ListNode mergeLists(ListNode[] lists, int i, int j) {
        // 终止条件是不可再拆
        if (i == j){
            return lists[i];
        }
        // 递的时候拆分记录链表的数组
        int median = (i + j) >>> 1;
        ListNode left = mergeLists(lists, i, median);
        ListNode right = mergeLists(lists, median + 1, j);
        // 归的时候两两链表合并
        return mergeTwoList1(left,right);
    }
}
